package a4_p04_jw_kw.euler;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

import org.jgrapht.Graph;
import org.jgrapht.graph.DefaultWeightedEdge;

import a1_p04_jw_kw.struct.GraphStatistic;
import a1_p04_jw_kw.struct.Node;

public class Fleury {
    ArrayList<DefaultWeightedEdge> eulerTour = new ArrayList<DefaultWeightedEdge>();
    Graph<Node, DefaultWeightedEdge> g;

    // bridge detection
    HashMap<Node, Integer> low = new HashMap<Node, Integer>();
    HashMap<Node, Integer> pre = new HashMap<Node, Integer>();

    ArrayList<DefaultWeightedEdge> marked = new ArrayList<DefaultWeightedEdge>();
    ArrayList<DefaultWeightedEdge> bridges;

    GraphStatistic stats = new GraphStatistic();
    int size;

    long clock;

    public Fleury(Graph<Node, DefaultWeightedEdge> g) {
        this.g = g;

    }

    public void createEulerTour() {
    	size = g.edgeSet().size();
    	
        startWatch();

        // suche bridges aus dem graphen
        detectBridges();

        Node currentNode = null;

        // 1. waehle beliebigen knoten als aktuellen knoten
        for (Node n : g.vertexSet()) {
            currentNode = n;
            break;

        }

        while (marked.size() != size) {
            Set<DefaultWeightedEdge> allEdges = g.edgesOf(currentNode);
            Set<DefaultWeightedEdge> edges = new HashSet<DefaultWeightedEdge>();

            // entferne markierte kanten
            for (DefaultWeightedEdge e : allEdges) {
                if (!marked.contains(e)) {
                    edges.add(e);

                }
            }

            // 2. Wähle unter den unmarkierten, mit dem aktuellen Knoten
            // inzidenten
            // Kanten eine beliebige Kante aus. Dabei sind zuerst Kanten zu
            // wählen,
            // die im unmarkierten Graphen keine Brückenkanten sind.
            detectBridges();
            
            Boolean bridgeOnly = true;
            DefaultWeightedEdge currentEdge = null;

            for (DefaultWeightedEdge e : edges) {
                if (!bridges.contains(e)) {
                    bridgeOnly = false;
                    currentEdge = e;
                    break;

                }
            }

            // wenn nur bruecken, waehle irgendeinen
            if (bridgeOnly) {
                for (DefaultWeightedEdge e : edges) {
                    currentEdge = e;
                    break;

                }
            }

            marked.add(currentEdge);
            eulerTour.add(currentEdge);
            g.removeEdge(currentEdge);

            // waehle neue kante
            if (g.getEdgeSource(currentEdge).equals(currentNode)) {
                currentNode = g.getEdgeTarget(currentEdge);

            } else {
                currentNode = g.getEdgeSource(currentEdge);

            }

        }

        stopWatch();

    }

    private void initializeBridgeDetection() {
        for (Node n : g.vertexSet()) {
            low.put(n, -1);
            pre.put(n, -1);
        }

        bridges = new ArrayList<DefaultWeightedEdge>();

    }

    private void detectBridges() {
        initializeBridgeDetection();

        for (Node n : g.vertexSet()) {
            if (pre.get(n) == -1) {
                detectBridgesRecursive(n, n);

            }
        }
    }

    private void detectBridgesRecursive(Node u, Node v) {
        pre.put(v, pre.get(v) + 1);
        low.put(v, pre.get(v));

        for (DefaultWeightedEdge edge : g.edgesOf(v)) {
            Node w;
            // wenn edge-source gleich v, dann muss das target der andere knoten
            // sein
            if (g.getEdgeSource(edge).equals(v)) {
                w = g.getEdgeTarget(edge);

                // wenn edge-source nicht gleich v, dann muss die source der
                // andere knoten sein
            } else {
                w = g.getEdgeSource(edge);

            }

            if (pre.get(w) == -1) {
                detectBridgesRecursive(v, w);
                low.put(v, Math.min(low.get(v), low.get(w)));

                if (low.get(v) == low.get(w)) {
                    bridges.add(edge);

                }
            } else if (!w.equals(u)) {
                low.put(v, Math.min(low.get(v), low.get(w)));

            }
        }

    }

    public GraphStatistic getStatistic() {
        return this.stats;

    }

    private void startWatch() {
        this.clock = System.currentTimeMillis();

    }

    private void stopWatch() {
        long stop = System.currentTimeMillis();
        stats.time = stats.time + (stop - clock);

    }

    public ArrayList<DefaultWeightedEdge> getEulerTour() {
        return eulerTour;

    }

}
